package de.uni.muenster.idw2.verbal.graph;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Locale;
import java.util.Scanner;

import de.uni.muenster.idw2.verbal.graph.INScanner;
import de.uni.muenster.idw2.verbal.choreme.ChoremeRoute;
import de.uni.muenster.idw2.verbal.test.ChoremeTest;



public class Graph {
	/**
	 * The set of all vertices for a floor
	 */
	private ArrayList<Vertex> V;
	/**
	 * The set of all edges for a floor
	 */
	private ArrayList<Edge> E;
	/**
	 * The set of all pairs for a floor
	 */
	private Pair[][] P;
	/**
	 * The set of all vertices that will lead to a new floor
	 */
	private ArrayList<Elevation> elevation;
	
	/**
	 * The set of all landmarks for a floor
	 */
	private ArrayList<Landmark> L;
	
	/**
	 * 
	 */
	private Path[] paths;
	
	/**
	 * used to increase efficiency of dijkstra's algorithm implementation.
	 * Contains indices of elements in paths[] that have isVisited=false and totalWeight<Integer.MAX_VALUE
	 */
	private ArrayList<Integer> unsettledPaths;
	
	/**
	 * Creates a shallow copy duplicate of Graph object
	 * @param V
	 * @param E
	 * @param elevation
	 * @param P
	 * @param L
	 */
	public Graph(ArrayList<Vertex> V, 
				 ArrayList<Edge> E, 
				 ArrayList<Elevation> elevation, 
				 Pair[][] P, 
				 ArrayList<Landmark> L){
		this.V = V;
		this.E = E;
		this.elevation = elevation;
		this.P = P;
		this.L = L;
		paths = new Path[E.size()];
		resetPaths();
	}
	
	public Graph(InputStream directory){
		V = new ArrayList<Vertex>();
		E = new ArrayList<Edge>();
		elevation = new ArrayList<Elevation>();
		P = null;
		//paths = new ArrayList<Path>();
		
		
		try {
//			Scanner scan1 = new Scanner(file);
//			scan1.useLocale(Locale.US);
			INScanner scan1 = new INScanner(directory);
			//Scanner scan2 = null;
			Vertex v1 = null;
			System.out.println("File read");
			
			//add vertices to V
			int numV = scan1.nextInt();
			scan1.nextLine();
			for(int i=0; i<numV; i++){
				//scan2 = new Scanner(scan1.nextLine());
				V.add(new Vertex(scan1.next(), new Coordinates(scan1.nextDouble(), scan1.nextDouble(), scan1.nextDouble())));
				scan1.nextLine();
				
			}
			
			//add Edges to E
			String eName, vert1, vert2;
			boolean[] found = new boolean[]{false, false};
			Vertex[] vArray = new Vertex[2];
			int numE = scan1.nextInt();
			scan1.nextLine();
			for(int i=0; i<numE; i++){
				//scan2 = new Scanner(scan1.nextLine());
				eName = scan1.next();
				vert1 = scan1.next();
				vert2 = scan1.next();
				scan1.nextLine();
				
				Iterator<Vertex> vIterator = V.iterator();
				vArray = new Vertex[2];
				found = new boolean[]{false, false};
				//search for vertices to link to edge
				int testCount=0;
				System.out.println("numE: "+i);
				vertexSearch:
				while(vIterator.hasNext()){
					System.out.println("\t"+testCount++);
					v1=vIterator.next();
					if(found[0]==false && v1.getName().equals(vert1)){
						vArray[0]=v1;
						if(found[1]==true){
							break vertexSearch;
						}
						else{
							found[0]=true;
						}
					}
					else if(found[1]==false && v1.getName().equals(vert2)){
						vArray[1]=v1;
						if(found[0]==true){
							break vertexSearch;
						}
						else{
							found[1]=true;
						}
					}
				}//end vertexSearch
				if(vArray[0]==null){
					System.out.println("1 is null");
				}
				if (vArray[1]==null){
					System.out.println("2 is null");
				}
				E.add(new Edge(eName, vArray));
			}//end for(eNum)
			
			//add elevations to "elevation"
			int elNum=scan1.nextInt();
			scan1.nextLine();
			for(int i=0; i<elNum; i++){
				Elevation el = new Elevation(scan1.nextInt());
				int numExits = scan1.nextInt();
				for(int exit=0; exit<numExits; exit++){
					String vName = scan1.next();
					Iterator<Vertex> vIterator = V.iterator();
					vertexSearch:
					while(vIterator.hasNext()){
						Vertex v= vIterator.next();
						if(v.getName().equals(vName)){
							el.add(v);
							break vertexSearch;
						}
					}//end vertexSearch
				}//end adding of exitPoints
				elevation.add(el);
				scan1.nextLine();
			}//end adding of Elevation objects
			
			//add pairs
			int pNum= scan1.nextInt();
			String pName, edge1, edge2, vMiddle;
			Edge eTemp;
			Vertex vTemp;
			Edge [] eArray=null;
			int posCount[] = null;
			P = new Pair[numE][numE];
			scan1.nextLine();
			for(int i=0; i<pNum; i++){
				System.out.println("pnum="+pNum);
				pName = scan1.next();
				edge1 = scan1.next();
				edge2 = scan1.next();
				vMiddle = scan1.next();
				//scan1.nextLine();
				
				//search for the two edges
				Iterator<Edge> eIterator = E.iterator();
				eArray = new Edge[2];
				posCount=new int[2];
				found = new boolean[]{false, false};
				//search for vertices to link to edge
				int count=0;
				System.out.println("numP: "+i);
				edgeSearch:
				while(eIterator.hasNext()){
					System.out.println("\t"+count);
					eTemp=eIterator.next();
					if(found[0]==false && eTemp.getName().equals(edge1)){
						eArray[0]=eTemp;
						posCount[0]=count;
						if(found[1]==true){
							break edgeSearch;
						}
						else{
							found[0]=true;
						}
					}
					else if(found[1]==false && eTemp.getName().equals(edge2)){
						eArray[1]=eTemp;
						posCount[1]=count;
						if(found[0]==true){
							break edgeSearch;
						}
						else{
							found[1]=true;
						}
					}
					count++;
				}//end edgeSearch
				
				//search for the central vertex
				Iterator<Vertex> vIterator = V.iterator();
				vTemp=null;
				vertexSearch:
				while(vIterator.hasNext()){
					Vertex v= vIterator.next();
					if(v.getName().equals(vMiddle)){
						vTemp=v;
						break vertexSearch;
					}
				}//end vertexSearch
				
				P[posCount[0]][posCount[1]] = new Pair(pName, vTemp, eArray, scan1.nextInt(), scan1.nextInt()); 
				scan1.nextLine();
			}
			
			for(Vertex v:V){
				System.out.println(v.getName() + " "+ v.getCoord().getFloor());
			}
			
			for(Edge e:E){
				System.out.print(e.getName() + " "); 
				Vertex vArray1[] = e.getVertices();
				System.out.print(vArray1[0].getName() + " ");
				System.out.println(vArray1[1].getName());
			}
			
			for(Elevation el:elevation){
				System.out.print(el.getFloorNum() + " ");
				ArrayList<Vertex> exits=el.getExitPoints();
				for(Vertex v:exits){
					System.out.print(v.getName()+" ");
				}
				System.out.println();
			}
			
//			for(Pair[]pRow:P){
//				for(Pair pCol:pRow){
//					if(pCol!=null){
//						System.out.println(pCol.getName() + " " +
//										   pCol.getEdges()[0].getName() + " " + 
//										   pCol.getEdges()[1].getName() + " " + 
//										   pCol.getInstruction() + " " + 
//										   pCol.getWeight());
//					}
//				}
//			}
			for(Pair[]pRow:P){
				for(Pair pCol:pRow){
					if(pCol!=null){
						System.out.print(pCol.getName()+"\t");
					}
					else{
						System.out.print("-\t");
					}
				}
				System.out.println();
			}
			
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			System.out.println("File could not be read.");
		} catch (IOException ioe) {
			// TODO Auto-generated catch block
			ioe.printStackTrace();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			System.out.println("File could not be read.");
		}
		//update paths
		paths = new Path[E.size()];
		for(Path newPath:paths){
			newPath=new Path();
		}
	}
	
	/*
	public static void main(String[] args){
		Graph g = new Graph("./graph.dat");
//		Graph g = new Graph("/home/jafar/codes/eclipse-indigo3.7.0/IndoorNaviVerbal/graph.dat");
//		ArrayList<Pair> pairList = g.getNextPairs(g.getE().get(1), g.getV().get(1));
//		for(Pair p:pairList){
//			System.out.println(p.getName());
//		}

//		Path pth = g.Dijkstra("R0.08", "R0.03");
		Path pth = g.Dijkstra("102", "106");
//		System.out.println("Path weight: "+pth.getTotalWeight());
//		ArrayList<Pair>prs = pth.getPairs();
//		System.out.println("Pairs used: ");
//		for(Pair pr:prs){
//			System.out.println(pr.getName());
//		}
		Pair[] pairs=new Pair[pth.getPairs().size()];
		pairs=pth.getPairs().toArray(pairs);
		System.out.println("Unchunked Pairs:");
		ChoremeTest.printPairs(pairs);
		System.out.println("Path weight: "+pth.getTotalWeight());
		ArrayList<Edge>edge = pth.getEdgesWithIntermediary();
		System.out.println("Edges used: ");
		for(Edge e:edge){
			System.out.println(e.getName());
		}
		
		System.out.println("Vertices used");
		ArrayList<Vertex> vList = pth.getVertices();
		for(Vertex v:vList){
			System.out.println(v.getName());
		}
		
		ChoremeRoute route = ChoremeRoute.generateChoreme(pairs);
		route = ChoremeRoute.applyDChoremeRule(route);
		route = ChoremeRoute.applyEChoremeRule(route);
		ChoremeTest.printChoremeRoute(route);

	}//end of main
	*/
	
	public Pair getFromMatrix(int row, int column){
		return P[row][column];
	}

	public ArrayList<Vertex> getV() {
		return V;
	}

	public ArrayList<Edge> getE() {
		return E;
	}

	public Pair[][] getP() {
		return P;
	}

	public ArrayList<Elevation> getElevation() {
		return elevation;
	}

	public ArrayList<Landmark> getL() {
		return L;
	}

	public Path[] getPaths() {
		return paths;
	}
	
	/**
	 * Given the current edge and the previous vertex, 
	 * this finds the other pairs associated with this edge and the next vertex.
	 * @param currentE
	 * @param previousV
	 * @return List of future pairs
	 */
	public ArrayList<Pair> getNextPairs(Edge currentE, Vertex previousV){
		ArrayList<Pair> nextPairs = new ArrayList<Pair>();
		return getNextPairs(getIndexOfEdge(currentE), previousV);
	}
	
	/**
	 * Given the index of the current edge and the previous vertex, 
	 * this finds the other pairs associated with this edge and the next vertex.
	 * @param currentE
	 * @param previousV
	 * @return List of future pairs
	 */
	public ArrayList<Pair> getNextPairs(int indexE, Vertex previousV){
		ArrayList<Pair> nextPairs = new ArrayList<Pair>();
		int length = P[indexE].length;
		Pair tempPair=null;
		for(int i=0; i<length; i++){
			
			tempPair = P[indexE][i];
			if(tempPair!=null 
					&& !tempPair.isVisited()
					&& !tempPair.getvCentral().getName().equals(previousV.getName())){
				nextPairs.add(tempPair);
			}
		}
		return nextPairs;
	}
	
	/**
	 * get the index of an edge
	 * @param e
	 * @return
	 */
	public int getIndexOfEdge(Edge e){
		//search for index of edge
		Iterator<Edge> eIterator = E.iterator();
		//search for vertices to link to edge
		int count=0;
		edgeSearch:
		while(eIterator.hasNext()){
			if(e.getName().equals(eIterator.next().getName())){
				break edgeSearch;
			}
			else{
				count++;	
			}
		}//end edgeSearch
		return count;
	}
	
	public Path getPathWithLowestDistance(){
		Path tempPath = new Path();
		int tempPathIndex= Integer.MAX_VALUE;
		for(int i=0; i<unsettledPaths.size(); i++){
			Path p = getPathOfEdge(unsettledPaths.get(i));
			if(p.isVisited()==false && p.getTotalWeight()<tempPath.getTotalWeight()){
				tempPath = p;
				tempPathIndex =i;
				
			}
		}
		if(tempPath.getTotalWeight()==Integer.MAX_VALUE){
			System.out.println("No more unsettled paths");
			return null;//there are no more available paths.
			
		}
		else{
			unsettledPaths.remove(tempPathIndex);
			return tempPath;
		}
	}
	
	private void evaluateNeighbouringEdges(Edge evaluationE, Vertex previousV){
		ArrayList<Pair> listP = getNextPairs(evaluationE, previousV);
		Path currentPath = getPathOfEdge(evaluationE);
		for(Pair pr:listP){
			Edge nextEdge = pr.getOtherEdge(evaluationE);
			Path nextPath = currentPath.duplication();
			nextPath.addPair(pr);
			//TODO: do chunking of nextPath here 
//			int nextWeight = Integer.MAX_VALUE;
//			if(currentPath.getTotalWeight()<0){
//				if(pr.getWeight()==Integer.MAX_VALUE){
//					System.out.println("ERROR: PAIR WEIGHT IS MAX_VALUE!!!!");
//				}
//				else if(pr.getWeight()<0){
//					System.out.println("ERROR: PAIR WEIGHT IS <0!!!!");
//				}
//			}
//			nextWeight = currentPath.getTotalWeight()+pr.getWeight();//TODO: replace addition with chunked weight here
			
			// Chunk Pair
			Pair[] pairs=new Pair[nextPath.getPairs().size()];
			pairs=nextPath.getPairs().toArray(pairs);
			System.out.println("Unchunked Pairs:");
			ChoremeTest.printPairs(pairs);
			
			Pair[] chunkedPairs=ChoremeRoute.chunkStraightPairs(pairs);
			System.out.println("Chunked Pairs:");
			ChoremeTest.printPairs(chunkedPairs);
			
			nextPath = new Path();
			for(int i=0;i<chunkedPairs.length;i++)
				nextPath.addPair(chunkedPairs[i]);
			
			// Test: generateChoreme()
			ChoremeRoute choreme=ChoremeRoute.generateChoreme(chunkedPairs);
			System.out.println("Chunked Choreme:");
			ChoremeTest.printChoremeRoute(choreme);
			// generateChoreme() test end //---
			
			int nextWeight = nextPath.getTotalWeight();
//			int nextWeight = currentPath.getTotalWeight()+pr.getWeight();//TODO: replace addition with chunked weight here
//			int nextWeight = nextPath.getTotalWeight();
//			if(nextWeight<0){
//				System.out.println("ERROR: TOTAL WEIGHT <0!!!!");
//			}
			int nextEdgeIndex = getIndexOfEdge(nextEdge);
			if(getPathOfEdge(nextEdgeIndex).getTotalWeight() > nextWeight){
				setPathOfEdge(nextPath, nextEdge);
				if(!unsettledPaths.contains(new Integer(nextEdgeIndex))){
					unsettledPaths.add(nextEdgeIndex);
					//System.out.println("unsettled:"+E.get(nextEdgeIndex).getName());
				}
				
			}
		}
	}
	
	private void resetPaths(){
		for(int i=0; i<paths.length; i++){
			paths[i]=new Path();
		}
	}
	
	private Path getPathOfEdge(Edge E){
		return paths[getIndexOfEdge(E)];
	}
	
	private Path getPathOfEdge(int index){
		return paths[index];
	}
	
	
	private void setPathOfEdge(Path path, Edge E){
		paths[getIndexOfEdge(E)] = path;
	}
	
	private void setPathOfEdge(Path path, int index){
		paths[index] = path;
	}
	
	public Path Dijkstra(String origin, String destination){
		return Dijkstra(getV().get(getIndexOfVwithName(origin)), getV().get(getIndexOfVwithName(destination)));
	}
	
	public Path Dijkstra(Vertex originV, Vertex destinationV){
		ArrayList<Edge> originEdges = getEdgesOfVertex(originV);
		ArrayList<Edge> destinationEdges = getEdgesOfVertex(destinationV);
		Path shortestPath = new Path();
		int shortestPathLength = Integer.MAX_VALUE;
		Path tempPath = null;
		int tempPathLength = Integer.MAX_VALUE;
		for(Edge oE:originEdges){
			for(Edge dE:destinationEdges){
				tempPath = DijkstraFromOneEdge(oE, dE, originV);
				tempPathLength = tempPath.getEdgesWithIntermediary().size();
				if(shortestPath.getTotalWeight() > tempPath.getTotalWeight()){
					shortestPath = tempPath;
					shortestPathLength = tempPathLength;
				}
				else if(shortestPath.getTotalWeight() == tempPath.getTotalWeight() && shortestPathLength>tempPathLength){
					shortestPath = tempPath;
					shortestPathLength = tempPathLength;
				}
			}
		}
		if(shortestPath.getTotalWeight()==Integer.MAX_VALUE){
			System.out.println("No shortest path found");
		}
		return shortestPath;
		
	}
	
	private ArrayList<Edge> getEdgesOfVertex(Vertex v){
		ArrayList<Edge> edgeList = new ArrayList<Edge>();
		for(Edge e:E){
			if(e.hasVertex(v)){
				edgeList.add(e);
			}
		}
		return edgeList;
	}
	
	public Path DijkstraFromOneEdge(Edge originE, Edge destinationE, Vertex originV){
		//TODO: dijkstra from one edge
		System.out.println("originE: "+ originE.getName());
		System.out.println("destinationE: "+destinationE.getName());
		System.out.println("originV: "+ originV.getName());
		
		resetPaths();
		unsettledPaths = new ArrayList<Integer>();
		int originEIndex = getIndexOfEdge(originE);
		System.out.println("originEIndex: "+ originEIndex);
		Path originPath = getPathOfEdge(originEIndex);
		//originPath.addPair(new Pair("oP", originV, new Edge[]{originE, originE}, ));
		if(originPath==null){
			System.out.println("path is null");
		}
		originPath.setTotalWeight(0);
		unsettledPaths.add(originEIndex);
		System.out.println("Path weight at origin: "+ getPathOfEdge(originEIndex).getTotalWeight());
		
		while(!unsettledPaths.isEmpty()){
			Path evaluationPath = getPathWithLowestDistance();
			evaluationPath.setVisited(true);
			//unsettledPaths.remove(evaluationPath.getTotalWeight());
			if(evaluationPath.getTotalWeight()==0){
				evaluateNeighbouringEdges(originE, originV);
			}else{
				Pair lastVisited = evaluationPath.getDestination();
				evaluateNeighbouringEdges(lastVisited.getEdge(1), lastVisited.getvCentral());
			}
			
		}
		
		//System.out.println(getPathOfEdge(destinationE).getTotalWeight());
		System.out.println();
		return getPathOfEdge(destinationE);
	}
	
	public int getIndexOfVwithName(String name){
		Iterator<Vertex> vIter = V.iterator();
		boolean found = false;
		int index=0;
		while(!found & vIter.hasNext()){
			if(vIter.next().getName().equals(name)){
				found=true;
			}
			else{
				index++;
			}
		}
		if(found){
			return index;
		}
		else{
			return Integer.MAX_VALUE;
		}
	}
}
